//
// Created by lxinp on 2023/5/16.
//

#ifndef DATASTRUCTURE_RBTREE_H
#define DATASTRUCTURE_RBTREE_H

using namespace std;


/**
 * Red-Black Tree
 * [Properties]
 * 1. Each node is either red or black;
 * 2. Root node is black;
 * 3. If a node is black, then both its children are red;
 * 4. For each node, all the paths starting from itself to leaves have the same number of black nodes;
 * 5. All leaf nodes are black [leaf nodes are null nodes];
 * [Implication]
 * These properties ensure that the longest path from the root will not exceed twice the length of the
 * shortest path (*).
 * 3 => There will be not contiguous red nodes.
 * [Proofs]
 * Assume there are N black nodes among all path starting from the root to all its leaves, then the
 * shortest path will consists only black nodes, i.e. length = N;
 * The longest path will switch from a black node to a red node, i.e. length = 2N;
 * These implies that the length of the longest path will <= 2 * (length of the shortest path).
 * @tparam K
 * @tparam V
 */
template<typename K, typename V>
class RBTree {
private:
    enum Color {
        Red,
        Black
    };

    struct RBNode {
        K key;
        V value;
        Color color;
        RBNode* left;
        RBNode* right;
        RBNode* parent;

        /**
         * Why picking Red as default>
         * Because inserting a black node will violate (4), but inserting a red node may or
         * may not violate (3).
         * @param _key
         * @param _value
         */
        RBNode(const K& _key, const V& _value) :
                key(_key), value(_value), color(Red),
                left(nullptr), right(nullptr), parent(nullptr) {}

        RBNode(const K& _key, const V& _value, Color _color) :
                key(_key), value(_value), color(_color),
                left(nullptr), right(nullptr), parent(nullptr) {}
    };

private:
    RBNode* root;

public:
    RBTree();
    RBTree(const RBTree& other);
    ~RBTree();
    RBTree& operator=(const RBTree& other);
    void clear();
    void insert(const K& key, const V& value);
    void remove(const K& key);
    V find(const K& key) const;

private:
    RBNode* copy(const RBNode* other);
    void clear(RBNode* subtree);
    void insert(RBNode* subtree, const K& key, const V& value);
    void remove(RBNode*& subtree, const K& key);
    V find(RBNode* subtree, const K& key) const;

    void rotate_left(RBNode*& node);
    void rotate_right(RBNode*& node);
    void rotate_left_right(RBNode*& node);
    void rotate_right_left(RBNode*& node);
};


#endif //DATASTRUCTURE_RBTREE_H
